package class07;

public class Code04_HorseJump {

	/**
	 * 暴力尝试 递归
	 * @param x
	 * @param y
	 * @param step
	 * @return
	 */
	public static int getWays(int x, int y, int step) {
		return process(x, y, step);
	}

	// 从(0,0)出发，要去往(x,y)位置，必须跳step步，返回方法数
	public static int process(int x, int y, int step) {
		// base case1 如果越界代表无法到达，返回方法数为0
		if (x < 0 || x > 8 || y < 0 || y > 9) {
			return 0;
		}
		// base case2 无步数了
		if (step == 0) {
			// 这里相当于做了一个反推，从(0,0)到(x,y)与从(x,y)到(0,0)是等价的
			// 相当于从终点往前推，如果步数没了，但是还没回到原点，说明此路不通
			return (x == 0 && y == 0) ? 1 : 0;
			/*
			 	这里也可以这么理解，因为(0,0)点是特殊的点
			 	如果终点是(0,0)，那么step==0也可以从原点到达(0,0)点，算是一种方法
			 	如果终点不是(0,0)，那么step==0则无法从原点到达非(0,0)点，此路不通
			 */
		}
		// 普通位置，到达的位置不越界，也有步数可以跳
		return process(x - 1, y + 2, step - 1)
				+ process(x + 1, y + 2, step - 1)
				+ process(x + 2, y + 1, step - 1)
				+ process(x + 2, y - 1, step - 1)
				+ process(x + 1, y - 2, step - 1)
				+ process(x - 1, y - 2, step - 1)
				+ process(x - 2, y - 1, step - 1)
				+ process(x - 2, y + 1, step - 1);
	}


	/**
	 * 记忆化搜索方式
	 * @param x
	 * @param y
	 * @param step
	 * @return
	 */
	public static int getWaysByMS(int x, int y, int step) {


		// 添加缓存
		// 可变参数，x，y，step
		// x:0~8 y:0~9
		int[][][] dp = new int[9][10][step+1];
		// 缓存初始化 因为格子里填写的方法数，若是不能到达方法数也就是0，因此不需要初始化为-1

		return process1(x, y, step, dp);
	}

	// 从(0,0)出发，要去往(x,y)位置，必须跳step步，返回方法数
	public static int process1(int x, int y, int step, int[][][] dp) {
		// ！！！ 只有不越界才能进行下面的判断，因此这个大条件要放到最头上
		// base case1 如果越界代表无法到达，返回方法数为0
		if (x < 0 || x > 8 || y < 0 || y > 9) {
			return 0;
		}

		// 缓存命中
		if(dp[x][y][step] != 0) {
			return dp[x][y][step];
		}

		// 缓存未命中
		// base case2 无步数了
		if (step == 0) {
			// 这里相当于做了一个反推，从(0,0)到(x,y)与从(x,y)到(0,0)是等价的
			// 相当于从终点往前推，如果步数没了，但是还没回到原点，说明此路不通
			dp[x][y][step] = (x == 0 && y == 0) ? 1 : 0;
		/*
			这里也可以这么理解，因为(0,0)点是特殊的点
			如果终点是(0,0)，那么step==0也可以从原点到达(0,0)点，算是一种方法
			如果终点不是(0,0)，那么step==0则无法从原点到达非(0,0)点，此路不通
		 */
		} else {
			// 普通位置，到达的位置不越界，也有步数可以跳
			dp[x][y][step] = process1(x - 1, y + 2, step - 1, dp)
					+ process1(x + 1, y + 2, step - 1, dp)
					+ process1(x + 2, y + 1, step - 1, dp)
					+ process1(x + 2, y - 1, step - 1, dp)
					+ process1(x + 1, y - 2, step - 1, dp)
					+ process1(x - 1, y - 2, step - 1, dp)
					+ process1(x - 2, y - 1, step - 1, dp)
					+ process1(x - 2, y + 1, step - 1, dp);
		}
		return dp[x][y][step];
	}


	/**
	 * 严格表结构DP
	 * @param x
	 * @param y
	 * @param step
	 * @return
	 */

	public static int dpWays(int x, int y, int step) {
		// base case1 未越界
		if (x < 0 || x > 8 || y < 0 || y > 9 || step < 0) {
			return 0;
		}
		int[][][] dp = new int[9][10][step + 1];

		// base case2 第0层的面
		dp[0][0][0] = 1;

		/* 普通位置 */
		for (int h = 1; h <= step; h++) { // 层  step层从 1 到 step。 第step==0的层已经在base case里填好了

			// 下面两个for循环是枚举x和y的值，因为同一层的没有依赖关系，for的顺序可以互换
			for (int r = 0; r < 9; r++) { // 行
				for (int c = 0; c < 10; c++) { // 列
					dp[r][c][h] += getValue(dp, r - 1, c + 2, h - 1);
					dp[r][c][h] += getValue(dp, r + 1, c + 2, h - 1);
					dp[r][c][h] += getValue(dp, r + 2, c + 1, h - 1);
					dp[r][c][h] += getValue(dp, r + 2, c - 1, h - 1);
					dp[r][c][h] += getValue(dp, r + 1, c - 2, h - 1);
					dp[r][c][h] += getValue(dp, r - 1, c - 2, h - 1);
					dp[r][c][h] += getValue(dp, r - 2, c - 1, h - 1);
					dp[r][c][h] += getValue(dp, r - 2, c + 1, h - 1);
				}
			}
		}
		return dp[x][y][step];
	}

	// 因为可能会越界，所以使用getValue
	// 结合上面的函数，如果越界则累加0，如果不越界，则累加格子值
	public static int getValue(int[][][] dp, int row, int col, int step) {
		if (row < 0 || row > 8 || col < 0 || col > 9) {
			return 0;
		}
		return dp[row][col][step];
	}




	// for test
	public static void main(String[] args) {
		int x = 7;
		int y = 7;
		int step = 10;
		System.out.println(getWays(x, y, step));
		System.out.println(getWaysByMS(x, y, step));
		System.out.println(dpWays(x, y, step));
	}
}
